package com.laotang.第_15_章_图论算法.力扣_133_克隆图;

import com.laotang.第_15_章_图论算法.图的DFS和BFS.Graph_DFS;

import java.util.*;

public class _133_clone_graph {

    class Node {
        public int val;
        public List<Node> neighbors;

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
    }

    public Node cloneGraph(Node node) {
        return dfs(node);
    }

    Map<Node, Node> visited = new HashMap<>();
    public Node dfs(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node newNode = new Node(node.val);
        visited.put(node, newNode);

        for (Node neighbor : node.neighbors) {
            newNode.neighbors.add(dfs(neighbor));
        }
        return newNode;
    }

}
